package _18_剑指OfferII;

import java.util.ArrayList;
import java.util.List;

public class _058_剑指OfferII日程表 {

    private List<int[]> containers;

    public _058_剑指OfferII日程表() {
        this.containers = new ArrayList<>();
        this.containers.add(new int[]{0, -1});
        this.containers.add(new int[]{Integer.MAX_VALUE, 0});
    }

    public boolean book(int start, int end) {
        int[] newEle = new int[]{start, end};
        int insertIndex = binarySearchInsertIndex(start);
        int[] next = containers.get(insertIndex);
        int[] prev = containers.get(insertIndex - 1);
        if (next[0] >= end && prev[1] <= start) {
            containers.add(insertIndex, newEle);
            return true;
        }
        return false;
    }

    private int binarySearchInsertIndex(int ele) {
        // 搜索容器起始位置的插入位置
        int begin = 0;
        // 找到大于其的数据
        int result = containers.size();
        int end = result - 1;
        while (begin <= end) {
            int mid = begin + ((end - begin) >> 1);
            if (containers.get(mid)[0] <= ele) {
                begin = mid + 1;
            } else {
                result = mid;
                end = mid - 1;
            }
        }
        return result;
    }

}
